CODE 34. Recover Binary Search Tree

版权声明：本文为博主原创文章，转载请注明出处，谢谢!

版权声明：本文为博主原创文章，转载请注明出处：http://blog.jerkybible.com/2013/09/20/2013-09-20-CODE 34 Recover Binary Search Tree/

访问原文「CODE 34. Recover Binary Search Tree」

Two elements of a binary search tree (BST) are swapped by mistake.
Recover the tree without changing its structure.
Note:
A solution using O(n) space is pretty straight forward. Could you devise a constant space solution?
confused what "{1,#,2,3}" means? >
read more on how binary tree is serialized on OJ.

OJ’s Binary Tree Serialization:The serialization of a binary tree follows a level order traversal, where ‘#’ signifies a path terminator where no node exists below.
Here’s an example:

  1
 / \
2   3
   /
  4
   \
    5

The above binary tree is serialized as "{1,2,3,#,#,4,#,#,5}".

public void recoverTree(TreeNode root) {
	// Start typing your Java solution below
	// DO NOT write main() function
	ArrayList<TreeNode> list = inorder(root);
	TreeNode err1 = null;
	TreeNode err2 = null;
	for (int i = 0; i < list.size() - 1; i++) {
		if (list.get(i).val > list.get(i + 1).val) {
			if (null == err1) {
				err1 = list.get(i);
			} else {
				err2 = list.get(i + 1);
				break;
			}
		}
	}
	if (null != err1 && null != err2) {
		int tmp = err1.val;
		err1.val = err2.val;
		err2.val = tmp;
	} else if (null != err1) {
		int index = list.indexOf(err1);
		int tmp = list.get(index + 1).val;
		list.get(index + 1).val = err1.val;
		err1.val = tmp;
	}
}

ArrayList<TreeNode> inorder(TreeNode node) {
	if (null == node.left && null == node.right) {
		ArrayList<TreeNode> list = new ArrayList<TreeNode>();
		list.add(node);
		return list;
	}
	ArrayList<TreeNode> list = null;
	if (null != node.left) {
		list = inorder(node.left);
	}
	if (null == list) {
		list = new ArrayList<TreeNode>();
	}
	list.add(node);
	if (null != node.right) {
		ArrayList<TreeNode> listRight = inorder(node.right);
		list.addAll(listRight);
	}
	return list;
}